package org.laizili.solution.nowcodertop101.list;

import org.laizili.structure.list.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&sfm=html&channel=nowcoder">BM12. 单链表的排序</a>
 * <p> 分治; 单向链表归并排序
 */
public class BM12 {
    private static class Solution {
        /**
         * @param head ListNode类 the head node
         * @return ListNode类
         */
        public ListNode sortInList(ListNode head) {
            // write code here
            if (head == null || head.next == null) {
                // 链表为空或链表只有一个结点
                return head;
            }
            ListNode midPrev = head;
            ListNode mid = head.next, fast = head.next.next;
            // 寻找中间结点，然后截断
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                midPrev = midPrev.next;
                mid = mid.next;
            }
            midPrev.next = null; // 截断链表
            return merge(sortInList(head), sortInList(mid)); // 返回合并结果
        }

        private ListNode merge(ListNode l1, ListNode l2) {
            ListNode head = new ListNode();
            ListNode cur = head;
            while (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    cur.next = l1;
                    l1 = l1.next;
                } else {
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            cur.next = l1 != null ? l1 : l2;
            return head.next;
        }
    }

    public static void main(String[] args) {
        // 1 3 2 4 5
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(4, node1);
        ListNode node3 = new ListNode(2, node2);
        ListNode node4 = new ListNode(3, node3);
        ListNode node5 = new ListNode(1, node4);
        ListNode cur = new Solution().sortInList(node5);
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }
}
